#include "router.hh"

#include <iostream>

using namespace std;

// Dummy implementation of an IP router

// Given an incoming Internet datagram, the router decides
// (1) which interface to send it out on, and
// (2) what next hop address to send it to.

// For Lab 6, please replace with a real implementation that passes the
// automated checks run by `make check_lab6`.

// You will need to add private members to the class declaration in `router.hh`

template <typename... Targs>
void DUMMY_CODE(Targs &&... /* unused */) {}

//! \param[in] route_prefix The "up-to-32-bit" IPv4 address prefix to match the datagram's destination address against
//! \param[in] prefix_length For this route to be applicable, how many high-order (most-significant) bits of the route_prefix will need to match the corresponding bits of the datagram's destination address?
//! \param[in] next_hop The IP address of the next hop. Will be empty if the network is directly attached to the router (in which case, the next hop address should be the datagram's final destination).
//! \param[in] interface_num The index of the interface to send the datagram out on.
void Router::add_route(const uint32_t route_prefix,
                       const uint8_t prefix_length,
                       const optional<Address>& next_hop, /* 当查找到下一跳地址为空时，说明从interface_num发出，即可到达目的地，所以下一跳地址可设为ip包里的目的地址 */
                       const size_t interface_num) {    /* 相当于路由器的端口 */
    cerr << "DEBUG: adding route " << Address::from_ipv4_numeric(route_prefix).ip() << "/" << int(prefix_length)
         << " => " << (next_hop.has_value() ? next_hop->ip() : "(direct)") << " on interface " << interface_num << "\n";

    // Your code here.
    if(prefix_length == 0){
        if(not _prefix_header->route_interface_num.has_value()){
            _prefix_header->route_interface_num = interface_num;
            _prefix_header->next_hop = next_hop;
        }
        return;
    }

    auto father_ptr = _prefix_header;
    uint8_t remain_len = prefix_length;
    uint8_t shift = 24;
    uint32_t mask = UINT8_MAX << shift;
    while(remain_len){
        uint8_t byte = (route_prefix & mask) >> shift;
        uint8_t byte_len = 8;
        if(remain_len < 8){
            byte &= ~(UINT8_MAX >> remain_len);
            byte_len = remain_len;
            remain_len = 0;
        }else
            remain_len -= 8;
        mask >>= 8;
        shift -= 8;

        // 父结点还没有map，创建
        if(not father_ptr->next_nodes_map.has_value())
            father_ptr->next_nodes_map = map<uint16_t, std::shared_ptr<PrefixNode>>{};

        uint16_t &&key = (static_cast<uint16_t>(byte_len) << 8) | static_cast<uint16_t>(byte);

        if(father_ptr->next_nodes_map->find(key) == father_ptr->next_nodes_map->end()){
            // map里没有该结点的记录
            (*father_ptr->next_nodes_map)[key] = make_shared<PrefixNode>(byte, byte_len);
//            auto &next = (*father_ptr->next_nodes_map)[key]->next_hop;
//            auto &num = (*father_ptr->next_nodes_map)[key]->route_interface_num;
            if(remain_len == 0){
                (*father_ptr->next_nodes_map)[key]->route_interface_num = interface_num;
                (*father_ptr->next_nodes_map)[key]->next_hop = next_hop;
            }
        }else{
            // map已有记录
            auto &next = (*father_ptr->next_nodes_map)[key]->next_hop;
            auto &num = (*father_ptr->next_nodes_map)[key]->route_interface_num;
            if(num.has_value() and *num == interface_num and next == next_hop){
                // 此时有结点，并且记录的下一跳的num和interface_num一致，则可以退出；比如将要add的route是此时遍历到的网络的子网
                break;
            }else if(remain_len == 0){
                // 此时的结点已是最后一个，且没有num数据，或者interface_num/next_hop和该结点的不一样，则记录/更新
                num = interface_num;
                next = next_hop;
            }
        }

        father_ptr = (*father_ptr->next_nodes_map)[key];
    }
}

// 查出目的地址（bytes）应该由哪个内部端口（interface）发出，以及由这个端口出去后的下一跳（next_hop）
std::pair<std::optional<Address>, std::optional<size_t>> Router::_getNextHopInfo(const array<uint8_t, 4> &bytes) {
    auto father_ptr = _prefix_header;
    optional<Address> next_hop = nullopt;
    optional<size_t> interface_num = nullopt;
    string addr;

    int i = 0;
    while(i <= 4){
        // 若父结点没有map，那很有可能父结点就是最大匹配的位置
        if(not father_ptr->next_nodes_map.has_value()) {
            next_hop = father_ptr->next_hop;
            interface_num = father_ptr->route_interface_num;
            break;
        }

        uint8_t mask;
        auto iter = father_ptr->next_nodes_map->rbegin();
        while(iter != father_ptr->next_nodes_map->rend()){
            mask = ((1 << iter->second->length) - 1) << (8 - iter->second->length);
            if((iter->second->byte & mask) == (bytes[i] & mask)){
                addr += to_string(iter->second->byte & mask) + ".";
                break;
            }
            ++iter;
        }
        if(iter != father_ptr->next_nodes_map->rend()){
            father_ptr = iter->second;
        }
        else{
            next_hop = father_ptr->next_hop;
            interface_num = father_ptr->route_interface_num;
            break;
        }

        ++i;

        //auto iter0 = father_ptr->next_nodes_map->lower_bound(static_cast<uint16_t>(bytes[i]));
        // key是byte | len，所以对于一个byte最大可匹配8位长度，对应key的数值自然也是最大的一个
        /*auto iter1 = father_ptr->next_nodes_map->upper_bound((static_cast<uint16_t>(bytes[i]) << 8) + 8);
        // iter1等于begin，说明没找到（都是比当前byte | len值大的），那最大只能匹配到父结点
        if(iter1 == father_ptr->next_nodes_map->begin()) {
            next_hop = father_ptr->next_hop;
            interface_num = father_ptr->route_interface_num;
            break;
        }
        --iter1;
        const uint8_t mask = ((1 << iter1->second->length) - 1) << (8 - iter1->second->length);
        if((iter1->second->byte & mask) != (bytes[i] & mask)) {
            next_hop = father_ptr->next_hop;
            interface_num = father_ptr->route_interface_num;
            break;
        }else {
            addr += to_string(iter1->second->byte & mask) + ".";
            father_ptr = iter1->second;
            ++i;
        }*/
    }
    cerr << "** matched addr is " << addr << endl;
    cerr << "* final node's byte is " << static_cast<int>(father_ptr->byte) << ", length is " << static_cast<int>(father_ptr->length) << endl;
    return {next_hop, interface_num};
}

inline std::pair<std::optional<Address>, std::optional<size_t>> Router::_getDefaultInfo() {
    return {_prefix_header->next_hop, _prefix_header->route_interface_num};
}

//! \param[in] dgram The datagram to be routed
// 将一个ip包route到下一跳的主机上（或路由端口）
void Router::route_one_datagram(InternetDatagram &dgram) {
    // Your code here.
    auto &header = dgram.header();
    auto &ttl = header.ttl;
    if(ttl == 0)
        return;

    auto *byte_arr = reinterpret_cast<uint8_t *>(&header.dst);
    array<uint8_t, 4> bytes{byte_arr[3], byte_arr[2],byte_arr[1],byte_arr[0]};
    auto nextHopInfo = _getNextHopInfo(bytes);

    cerr << "* next_hop is " << (nextHopInfo.first.has_value()? nextHopInfo.first->to_string() : "null")
         << ", interface is " << (nextHopInfo.second.has_value()? to_string(*nextHopInfo.second) : "none") << endl;
    if(not nextHopInfo.first.has_value()) {
        if (nextHopInfo.second.has_value()) {
            // 若interface_num有值，此时说明下一跳就是目的地
            nextHopInfo.first = Address::from_ipv4_numeric(dgram.header().dst);
        }else{
            // 若interface_num为空，此时说明未匹配到，便走默认路由
            nextHopInfo = _getDefaultInfo();
            // nextHopInfo.second = 0;
        }
    } else if(ttl == 1)
        // 若next_hop不为空，说明下一跳不是目的地，所以ttl=1的话，肯定不够，所以丢弃
        return;
    --ttl;

    interface(*nextHopInfo.second).send_datagram(dgram, *nextHopInfo.first);
}

void Router::route() {
    // Go through all the interfaces, and route every incoming datagram to its proper outgoing interface.
    for (auto &interface : _interfaces) {
        auto &queue = interface.datagrams_out();
        while (not queue.empty()) {
            route_one_datagram(queue.front());
            queue.pop();
        }
    }
}

std::array<uint8_t, 4> Router::_route_default = {0, 0, 0, 0};